package com.cdream.basic.algorithm.leetcode.dfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cdream
 * @date 8/24/21
 */
public class Question787 {
    public static void main(String[] args) {
        new Question787().findCheapestPrice(3,new int[][]{{0,1,2},{1,2,1},{2,0,10}},1,2,1);
    }
    int min = Integer.MAX_VALUE;
    Map<Integer,List<int[]>> map;
    boolean used[] = new boolean[101];
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        map = new HashMap<>();
        for(int i = 0; i<flights.length;i++){
            List<int[]> list = map.getOrDefault(flights[i][0],new ArrayList<>());
            list.add(flights[i]);
            map.put(flights[i][0], list);
        }
        dfs(src,dst , k+1, 0);
        return min == Integer.MAX_VALUE? -1:min;
    }
    void dfs(int src, int dst, int step, int money){
        if(step==0){
            if(src==dst){
                min = money;
            }
            return;
        }
        if (step>0 && src==dst){
            min = money;
            return;
        }

        List<int[]> nexts= map.get(src);
        for(int[] next: nexts){
            if(used[next[0]]){
                continue;
            }
            if(money + next[2]>=min){
                continue;
            }
            used[next[0]] = true;
            dfs(next[1],dst,step-1,money + next[2]);
            used[next[0]] = false;
        }

    }
}
